package q73_setZeroes;

import CommonClass.Common;

public class Solution_2 {
    public static void main(String[] args) {
        Solution_2 s = new Solution_2();
        int[][] arr1 = new int[][]{{1,1,1}, {1,0,6},{1,1,1}};
        s.setZeroes(arr1);

        Common c = new Common();
        c.printMatrix(arr1);


    }

    /**
     * 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间
     * 但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。
     * 因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
     * 在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，
     * 然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        // 先遍历第一行和第一列有没有出现0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
            }
        }

        // 然后直接使用第一行和第一列，记录这一行和这一列是否有0，
        // 实际上如果该行或者该列出现0，那么第一行/列对应的位置也会被置0，因此可以使用该方法
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 最后再使用flag检验，如果第一行/列原来就有0，那么再将对应的行/列置0
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

    }
}
